#ifndef __NONOVERLAPSECTION__
#define __NONOVERLAPSECTION__
#include <vector>
#include <algorithm>

typedef struct Section {
	int Start;
	int End;
}Section;

bool CompareSectionsByEnd(const Section& s1, const Section& s2) {
	return s1.End < s2.End;
}

/*
* 无重叠区间
* 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠
*/
int NonOverlapSection(vector<Section>& sections) {
	//让区间根据终点升序排序
	sort(sections.begin(), sections.end(), CompareSectionsByEnd);

	int result = 0;
	int max_end = sections[0].End;
	for (int i = 1; i < sections.size(); i++) {
		//起点小于最大终点时，需要移除该区间
		if (sections[i].Start < max_end)
			result++;

		else
			max_end = sections[i].End;
	}

	return result;
}

#endif // !__NONOVERLAPSECTION__
